#define _CRT_SECURE_NO_WARNINGS 1
char chang[4] = { 'A','C','T','G' };
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        int len = bank.size();
        unordered_map<string, int>mp;
        for (int i = 0; i < len; i++) {
            mp[bank[i]]++;
        }
        queue<string> q;
        q.push(startGene);
        int d = 0;
        unordered_map<string, int> st;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();
                if (st[it])continue;
                if (it == endGene)return d;
                st[it]++;
                for (int j = 0; j < it.size(); j++) {

                    for (int z = 0; z < 4; z++) {
                        if (chang[z] == it[j])continue;
                        string res = it;
                        res[j] = chang[z];
                        if (mp[res] && !st[res]) {
                            q.push(res);
                        }
                    }
                }
            }
            d++;
        }
        return -1;
    }
};